import java.io.PrintStream;



public class RegAlloc implements CGConstants {
    private static final int
    R_eq_R_op_R = 0,
    S_eq_R_op_R = 1,
    R_eq_S_op_R = 2,
    S_eq_S_op_R = 3,
    R_eq_R_op_S = 4,
    S_eq_R_op_S = 5,
    R_eq_S_op_S = 6,
    S_eq_S_op_S = 7;

    private RegDesc[] registers;

    private PrintStream out;

    public RegAlloc(PrintStream out) {
        this.out = out;
        registers = new RegDesc[R_MAX];

        for (int i = 0; i < R_MAX; i++) registers[i] = new RegDesc(i);
    }

    /**
     * spilling of all registers. Values are dumped in memory if necessary
     */
    public void spillAll() {
        for (int i = R_RES; i < R_MAX; i++)
            registers[i].spill(i, this.out);
    }

    /**
     * flushAll: spill all registers and clear their descriptors
     */
    public void flushAll() {
        for (int i = R_RES; i < R_MAX; i++) {
            registers[i].spill(i, this.out);
            registers[i].clear();
        }
    }
    /**
     * clear a descriptor
     */

    public void clearDescriptor(int r) {
        registers[r].clear();
    }

    /**
     * clear all descriptors
     */
    public void clearAll() {
        for (int i = R_RES; i < R_MAX; i++) {
            registers[i].clear();
        }
    }

    /**
     * spill a register
     */
    public void spillOne(int r) {
        registers[r].spill(r, this.out);
    }


    /**
     * load a value in a register.
     * The register descriptor is updated accordingly
     */

    public void loadRegisterMIPS(int r, Operand3a op) {
        // look if it is in a register
        for (int s = 0; s < R_MAX; s++) {
            if (registers[s].getMemory() == op) {
                out.println(R_INDENT + "move  $" + r + ",$" + s);
                setDescriptor(r, op, registers[s].getModif());
                return;
            }
        }

        // not in a register. Load appropriately with type
        if (op.isConstInteger()) {
            out.println(R_INDENT + "li   $" + r + ", " + op.getName3a());
        } else {
            if (op.isVarInteger()) {
                out.println(R_INDENT + "lw  $" + r + "," + op.getOffset() + "($" + R_STACK + ")");
            } else if (op.isPointer()) {//different from local array
                out.println(R_INDENT + "lw  $" + r + "," + op.getOffset() + "($" + R_STACK + ")");
            } else {
                if (op.isLabel()) {
                    // special case of print string
                    out.println(R_INDENT + "lui   $" + r + ",%hi(" + op.getName3a() + ")");
                    out.println(R_INDENT + "addiu   $" + r + ",$" + r + ",%lo(" + op.getName3a() + ")");
                } else {
                    System.out.println("\n loadRegister: unknown case");
                }
            }
        }

        registers[r].set(op, R_UNMODIFIED);
    }


    public void loadRegisterMIPS(RegDesc r, Operand3a op) {
        this.loadRegisterMIPS(r.getRegNumber(), op);
    }



    /**
     * insert a descriptor entry for the given name
     */
    public void setDescriptor(int r, Operand3a mem, boolean mod) {
        // check if it is already in a register
        for (int re = R_GEN; re < R_MAX; re++)
            if (registers[re].getMemory() == mem) registers[re].clear();

        registers[r].set(mem, mod);
    }

    /**
     * search for a symbol in a register, return -1 if not found
     */
    public int search(Operand3a mem) {
        int r;

        for (r = R_GEN; r < R_MAX; r++)
            if (registers[r].getMemory() == mem) break;

        if (r < R_MAX) return r;
        else return -1;
    }


    /**
     * getErasable gets a register that will hold an operand and be
     * overwritten by  the result.
     */
    public int getErasable(Operand3a op) {
        /*  get a register to hold the result of a computation a := b op c
         * This must initially hold c and will be overwritten with a. If c
         * is already in a register we use that, spilling it if necessary.
         * Otherwise we use in order of preference from: 1) an empty register;
         * 2) an unmodified register; 3) a modified register.
         * In the last case we spill the content of the register before it
         * is used. If c is not in the given result register, we load it.
         * Clearly, we must use only general purpose registers. Note that
         * since c may be the same as b, we must update the address and
         * register descriptors
         */
        int r;

        // already in a register?
        for (r = R_GEN; r < R_MAX; r++)
            if (registers[r].getMemory() == op) {
                registers[r].spill(r, this.out);
                return r;
            }

        // find an empty register?
        for (r = R_GEN; r < R_MAX; r++)
            if (registers[r].getMemory() == null) {
                loadRegisterMIPS(r, op);
                return r;
            }

        // find an unmodified register?
        for (r = R_GEN; r < R_MAX; r++)
            if (!registers[r].getModif()) {
                registers[r].clear();
                loadRegisterMIPS(r, op);
                return r;
            }

        // take a modified register
        registers[R_GEN].spill(R_GEN, this.out);
        registers[R_GEN].clear();
        loadRegisterMIPS(R_GEN, op);
        return R_GEN;
    }

    /**
     * getAnother get a register to hold the second operand of a computation
     */
    public int getAnother(Operand3a op, int cr) {
        int r;

        // already in a register?
        for (r = R_GEN; r < R_MAX; r++)
            if (registers[r].getMemory() == op && r != cr) {
                return r;
            }

        // find an empty register?
        for (r = R_GEN; r < R_MAX; r++)
            if (registers[r].getMemory() == null && r != cr) {
                loadRegisterMIPS(r, op);
                return r;
            }

        // find an unmodified register?
        for (r = R_GEN; r < R_MAX; r++)
            if (!registers[r].getModif() && (r != cr)) {
                registers[r].clear();
                loadRegisterMIPS(r, op);
                return r;
            }

        // take a modified register different from cr
        for (r = R_GEN; r < R_MAX; r++)
            if (r != cr) {
                registers[r].spill(r, this.out);
                registers[r].clear();
                loadRegisterMIPS(r, op);
                return r;
            }

        return -1; // this should never happend
    }

    /**
     * get some register: get a register without associating it with some
     * place in memory. We use the same policy as above to select it
     */

    public int getSome(int cr) {
        int r;

        // find an empty register?
        for (r = R_GEN; r < R_MAX; r++)
            if (registers[r].getMemory() == null) {
                return r;
            }

        // find an unmodified register?
        for (r = R_GEN; r < R_MAX; r++)
            if (!registers[r].getModif() && (r != cr)) {
                registers[r].clear();
                return r;
            }

        // take a modified register (necessarely not cr as this one is newly loaded)
        registers[R_GEN].spill(R_GEN, this.out);
        registers[R_GEN].clear();
        return R_GEN;
    }

    public RegDesc getEmptyRegister() {
        int r;

        for (r = R_GEN; r < R_MAX; r++)
            if (registers[r].getMemory() == null)
                return registers[r];

        return null;
    }

    //get an empty register different from r1 if it exists
    public RegDesc getEmptyRegister(int r1) {
        int r;

        for (r = R_GEN; r < R_MAX; r++)
            if (registers[r].getMemory() == null && r != r1)
                return registers[r];

        return null;
    }

    //get an empty register different from r1 and r2 if it exists
    public RegDesc getEmptyRegister(int r1, int r2) {
        int r;

        for (r = R_GEN; r < R_MAX; r++)
            if (registers[r].getMemory() == null && r != r1 && r != r2)
                return registers[r];

        return null;
    }


    public RegDesc getNotModifiedRegister() {
        int r;

        for (r = R_GEN; r < R_MAX; r++)
            if (registers[r].getModif() == false)
                return registers[r];

        return null;
    }


    //get a not modified register different from r1 if it exists
    public RegDesc getNotModifiedRegister(int r1) {
        int r;

        for (r = R_GEN; r < R_MAX; r++)
            if (registers[r].getModif() == false && r != r1)
                return registers[r];

        return null;
    }

    //get a not modified register different from r1 and r2 if it exists
    public RegDesc getNotModifiedRegister(int r1, int r2) {
        int r;

        for (r = R_GEN; r < R_MAX; r++)
            if (registers[r].getModif() == false && r != r1 && r != r2)
                return registers[r];

        return null;
    }


    public RegDesc isInRegister(Operand3a op) {
        int r = this.search(op);

        if (r == -1)
            return null;
        else
            return  registers[r];
    }


    public RegDesc allocateOneRegister() {
        RegDesc reg;

        reg = this.getEmptyRegister();

        if (reg != null)
            return reg;

        reg = this.getNotModifiedRegister();

        if (reg != null)
            return reg;

        reg = this.registers[R_GEN];
        this.spillOne(R_GEN);
        return reg;
    }


    //allocate a register different from r1
    public RegDesc allocateOneRegister(int r1) {
        RegDesc reg;

        reg = this.getEmptyRegister(r1);

        if (reg != null) {
            return reg;
        }

        reg = this.getNotModifiedRegister(r1);

        if (reg != null) {
            return reg;
        }

        for (int r = R_GEN; r < R_MAX; r++) {
            if (r != r1) {
                reg = this.registers[r];
                this.spillOne(r);
                return reg;
            }
        }

        return null;
    }

    //allocate a register different from r1 and r2
    public RegDesc allocateOneRegister(int r1, int r2) {
        RegDesc reg;

        reg = this.getEmptyRegister(r1, r2);

        if (reg != null)
            return reg;

        reg = this.getNotModifiedRegister(r1, r2);

        if (reg != null)
            return reg;

        for (int r = R_GEN; r < R_MAX; r++) {
            if (r != r1 && r != r2) {
                reg = this.registers[r];
                this.spillOne(r);
                return reg;
            }
        }

        return null;
    }


    /**
     * Allocate three registers for a 3-addresses opcode
     *
     * @param dest
     * @param op1
     * @param op2
     * @return
     */
    public Triplet<RegDesc> allocateRegisters(Operand3a dest, Operand3a op1, Operand3a op2) {
        // Each operand can be in two states:
        // - Already bound to a register (nothing to be done)
        // - Not bound to a register (we need to find one).
        // 2^3 cases have to be considered.

        RegDesc destReg = this.isInRegister(dest);
        RegDesc op1Reg = this.isInRegister(op1);
        RegDesc op2Reg = this.isInRegister(op2);
        int destInRegister = (destReg != null) ? 0 : 1 ;
        int op1InRegister = (op1Reg != null) ? 0 : 2 ;
        int op2InRegister = (op2Reg != null) ? 0 : 4 ;
        int situation = destInRegister + op1InRegister + op2InRegister;

        switch (situation) {
        case R_eq_R_op_R:
            // All three operands are already associated to registers
            break;
        case S_eq_R_op_R:

            if (!op1Reg.getModif()) {
                destReg = op1Reg;
                break;
            }

            if (!op2Reg.getModif()) {
                destReg = op2Reg;
                break;
            }

            destReg = this.allocateOneRegister(op1Reg.getRegNumber(), op2Reg.getRegNumber());
            break;
        case R_eq_R_op_S:
            op2Reg = destReg;
            this.loadRegisterMIPS(op2Reg, op2);
            break;
        case R_eq_S_op_R:
            op1Reg = destReg;
            this.loadRegisterMIPS(op1Reg, op1);
            break;
        case S_eq_R_op_S:
            op2Reg = this.allocateOneRegister(op1Reg.getRegNumber());
            this.loadRegisterMIPS(op2Reg, op2);
            destReg = op2Reg;
            break;
        case S_eq_S_op_R:
            op1Reg = this.allocateOneRegister(op2Reg.getRegNumber());
            this.loadRegisterMIPS(op1Reg, op1);
            destReg = op1Reg;
            break;
        case R_eq_S_op_S:
            op1Reg = destReg;
            this.loadRegisterMIPS(op1Reg, op1);
            op2Reg = this.allocateOneRegister(op1Reg.getRegNumber());
            this.loadRegisterMIPS(op2Reg, op2);
            break;
        case S_eq_S_op_S:
            destReg = this.allocateOneRegister();
            op2Reg = destReg;
            op1Reg = this.allocateOneRegister(destReg.getRegNumber());
            this.loadRegisterMIPS(op1Reg, op1);
            this.loadRegisterMIPS(destReg, op2);

            break;
        }

        // In all cases the destination register now contains a value associated
        // with dest operand, and it has been modified.
        destReg.set(dest, true);

        return new Triplet<RegDesc>(destReg, op1Reg, op2Reg);
    }

}
